home *** CD-ROM | disk | FTP | other *** search
/ NetNews Offline 2 / NetNews Offline Volume 2.iso / news / comp / lang / c-part1 / 9087 < prev    next >
Encoding:
Text File  |  1996-08-05  |  2.0 KB  |  44 lines
  1. Newsgroups: comp.lang.c
  2. Path: cwi.nl!dik
  3. From: dik@cwi.nl (Dik T. Winter)
  4. Subject: Re: Nedd help!!! <depth of recursion>
  5. Message-ID: <DnxDzy.HL0@cwi.nl>
  6. Sender: news@cwi.nl (The Daily Dross)
  7. Nntp-Posting-Host: chrysant.cwi.nl
  8. Organization: CWI, Amsterdam
  9. References: <JSA.96Mar7145352@organon.com> <Pine.SUN.3.91.960307161803.17639A-100000@thomas.helios.nd.edu> <4hnrol$5ts@umbc9.umbc.edu>
  10. Date: Fri, 8 Mar 1996 01:40:45 GMT
  11.  
  12. In article <4hnrol$5ts@umbc9.umbc.edu> schlein@umbc.edu (Jonas J. Schlein) writes:
  13. [ About the Ackerman function ].
  14.  > |> My problem is computing the depth of recursion of the procedure <Ack(m,n)>.
  15.  > |> Ack(m,n) = {n+1        if    m=0
  16.  > |>         Ack(m-1,n)    if    n=0
  17.  > |>         Ack(m-1,Ack(m,n-1)     }
  18. [ Note, this is not the true Ackerman function; the last line is wrong and
  19. should read "Ack(m-1,Ack(m,n-1)+1)}" I think.]
  20.  
  21.  > Well I highly suspect this is a homework assignment since you are
  22.  > posting from a *.edu site. However, I will give you this hint...Add
  23.  > a global variable to your program called 'depth' and increment it everytime
  24.  > Ack() is called.
  25.  
  26. This will not count the depth but the number of calls.  To count the
  27. depth you need two globals.  A question is of course how the third line
  28. ought to count with respect to recursion depth.  Should the Ack in
  29. the parameter list counter deeper in recursion as the plain Ack or not?
  30. (In old times this was indeed also called recursion, currently it is
  31. different I think.)
  32.  
  33. Another hint, do not try the function with large parameters (like integers
  34. exceeding 3 or something like that).  And make the globals long's if your
  35. int's are only 16 bits.  (With the redefinition Ack(3,2) gives a depth of
  36. 32770; which looks about right.)
  37.  
  38. Note: in the modified definition Ack(0,n) == n + 1; Ack(1,n) == 2*(n+2) - 3
  39. and Ack(2,n) == 2**(n+2) - 3 which is as I remember it.
  40. (** is exponentiation.)
  41. -- 
  42. dik t. winter, cwi, kruislaan 413, 1098 sj  amsterdam, nederland, +31205924098
  43. home: bovenover 215, 1025 jn  amsterdam, nederland; http://www.cwi.nl/~dik/
  44.